76. Minimum Window Substring

Solution 1: Slide Window + Hash

from collections import Counter 

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        charFrequencyHash = collections.Counter(t)
        requiredSubStrCnt = len(t)
        startIdxOfSubStr, endIdxOfSubStr = 0, 0
        lftWindowIdx = 0
        for rhtWindowIdx in range(len(s)):
            # After Init Counter, the count of the required char in substr is > 0 
            char = s[rhtWindowIdx]
            if charFrequencyHash[char] > 0:
                requiredSubStrCnt -= 1 
            charFrequencyHash[char] -= 1
            
            # print('rhtWindowIdx = ', rhtWindowIdx, charFrequencyHash)
            
            # Substr is found
            if requiredSubStrCnt == 0:
                # print("SubStr is set!")
                
                # scan to rhtWindow, and remove the non-targer char
                while lftWindowIdx <= rhtWindowIdx and charFrequencyHash[s[lftWindowIdx]] < 0:
                    charFrequencyHash[s[lftWindowIdx]] += 1
                    lftWindowIdx += 1
                
                # print('After While, ', charFrequencyHash)
                
                # Update window
                if (endIdxOfSubStr == 0) or ((rhtWindowIdx - lftWindowIdx + 1) < (endIdxOfSubStr - startIdxOfSubStr)):
                    startIdxOfSubStr, endIdxOfSubStr = lftWindowIdx, rhtWindowIdx + 1
                    # print('startIdxOfSubStr, endIdxOfSubStr = ', startIdxOfSubStr, endIdxOfSubStr)
                
                # Found the first target char (Freq == 0), remove it and try to find it in future
                charFrequencyHash[s[lftWindowIdx]] += 1
                requiredSubStrCnt += 1
                lftWindowIdx += 1 # Remove head of founded substr
        return s[startIdxOfSubStr: endIdxOfSubStr]

Time Complexity: O(N^2)
Space Complexity: O(N)

Reference

https://leetcode.com/problems/minimum-window-substring/discuss/26804/12-lines-Python
https://medium.com/leetcode-%E6%BC%94%E7%AE%97%E6%B3%95%E6%95%99%E5%AD%B8/035-leetcode-76%E6%BC%94%E7%AE%97%E6%B3%95-minimum-window-substring-%E6%9C%80%E5%B0%8F%E7%AA%97%E5%8F%A3%E5%AD%90%E5%AD%97%E4%B8%B2-6513c9ef03f4